// Given a sequence of n integers, determine a contiguous subsequence Ai...Aj
// for which the sum of elements in the subsequence is maximized.
//
// Algorithm: Dynamic Programming
// Let M(i) denote the maximum sum over all windows ending at i
//
// Then,
//   M(i)=max{M(i-1)+A[i], A[i]}, 1=<i<n
//   M(0)=A[0]
//
// Therefore,
//   The max{M[i]|0<=i<n} is a solution to the problem
//
// Complexity:
//   Time: O(n)
//   Space: O(1) - Iteration
//          O(n) - Recursion

#include "stdafx.h"
#include <iostream>
using namespace std;

#define max(a, b) (((a)>(b))?(a):(b))

// Iteration - O(1) space
int MaxSum_Iteration(int *p, int n)
{
	if(!p||n<=0) throw; // invalid inputs

	int maxSum, sum;
	maxSum=sum=p[0];

	for(int i=1; i<n; i++)
	{
		sum=(sum>0) ? sum+p[i] : p[i]; // need to check integer overflows: A+B-A!=B
		maxSum=(maxSum<sum) ? sum : maxSum;
	}

	return maxSum;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int p[]={ 2, -1, 2, -1 };
	int n=sizeof(p)/sizeof(p[0]);

	cout<<"Array: { ";
	for(int i=0;i<n;i++) cout<<p[i]<<(i<n-1?", ":"");
	cout<<" }"<<endl;
	cout<<"Max Sum: "<<MaxSum_Iteration(p,n);
	return getchar();
}